public class ReachablePoints {

+
	static int minJumps(int a[], int n)
	{
		//create jumps array
		int[] jumps = new int[n];
		//last element needs o jumps 
		jumps[n-1]=0;
		//Start for second last element and go from right to left. 
		for(int i = n-2; i>=0; i--)
		{
			//if nothing is reachable
			if(a[i] == 0)
				jumps[i] = Integer.MAX_VALUE;

			//if end is reachable
			if(a[i]>=n-i-1)
				jumps[i] = 1;

			//otherwise, find min of jumps of all points reachable from i

			else
			{
				int min = Integer.MAX_VALUE;
				for(int j = i+1; j < n && j <= i + a[i]; j++)
				{
					if(min > jumps[j])
						min = jumps[j];
				}

				//Handle overflows
				if(min != Integer.MAX_VALUE)
					jumps[i] = min+1;
				else
					jumps[i] = Integer.MAX_VALUE; 
			}

		}

		return(jumps[0]);
	}

	public static void main(String[] args) {
	

    int a[]= {1, 3, 5, 8, 9, 2 ,6 ,7 ,6 ,8 ,9 };
    int n=a.length;
    System.out.println("Minimum number of jumps to reach end is  "+ minJumps(a,n));
    //return 0;

	}
	
}